package com.list;

import com.tgy.util.AbstractList;

/**
 * @Author: tgy
 * @Date: 2020-08-28 09:35
 */
public class LinkedList<E> extends AbstractList<E> {

    private Node<E> firstNode;

    private static class Node<E>{

        E element;
        Node next;

        Node(E element, Node next) {
            this.element = element;
            this.next = next;
        }
    }

    @Override
    public E get(int index) {

        return elementOf(index).element;
    }

    @Override
    public E set(int index, E element) {

        checkIndex(index);
        Node<E> beforeNode = null;
        if (index == 0){

            beforeNode = firstNode;
            Node<E> newNode = new Node<>(element, firstNode.next);

            firstNode = newNode;
        }else {

            Node<E> eNode = elementOf(index - 1);

            beforeNode = eNode.next;

            Node<E> newNode = new Node<>(element, eNode.next.next);
            eNode.next = newNode;
        }

        return beforeNode.element;
    }

    @Override
    public void add(int index, E element) {

        if (index == 0){

            Node<E> newNode = new Node<>(element, firstNode);
            firstNode = newNode;
        }else {

            Node<E> eNode = elementOf(index - 1);

            Node<E> newNode = new Node<>(element, eNode.next);
            eNode.next = newNode;
        }

        size++;
    }

    @Override
    public E remove(int index) {

        checkIndex(index);

        Node<E> removeNode = null;

        if (index == 0){

            // 如果链表为空，firstNode 为 null， firstNode.next 会报NPE
            removeNode  = firstNode;
            firstNode = firstNode.next;

        }else {

            Node<E> eNode = elementOf(index - 1);

            removeNode = eNode.next;

            eNode.next = eNode.next.next;
        }

        size--;
        return removeNode.element;
    }

    @Override
    public int indexof(E element) {


        Node<E> tmpNode = firstNode;

        if (element == null){

            for (int i = 0; i < size; i++) {

                if (tmpNode.element == null) {

                    return i;
                }

                tmpNode = tmpNode.next;
            }
        }else {

            for (int i = 0; i < size; i++) {

                if (element.equals(tmpNode.element)){

                    return i;
                }

                tmpNode = tmpNode.next;
            }

        }

        return NOT_FOUND_ELEMENT;
    }

    @Override
    public void clear() {

        size = 0;
        firstNode = null;
    }


    @Override
    public String toString() {

        StringBuilder stringBuilder = new StringBuilder("size=");
        stringBuilder.append(size);

        stringBuilder.append(" [");
        Node<E> tmpNode = firstNode;

        for (int i = 0; i < size; i++) {

            if (i != 0){

                stringBuilder.append(",");
            }

            stringBuilder.append(tmpNode.element);

            tmpNode = tmpNode.next;
        }

        stringBuilder.append("]");
        return stringBuilder.toString();
    }


    /**
     * 递归方式
     */
    public void reversalByRecursion(){

        firstNode = doReversalByRecursion(firstNode);
    }

    /**
     * 迭代方式
     */
    public void reversalByIterator() {

        doReversalByIterator();
    }

    /**
     * 判断
     * @return
     */
    public boolean isCircle(){

        if (firstNode == null && firstNode.next == null){

            return false;
        }

        Node<E> slowNode = firstNode;
        Node<E> fastNode = firstNode.next;

        while (slowNode.next != null && fastNode.next.next != null){

            if (slowNode == fastNode){

                return true;
            }

            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }

        return false;
    }

    private void doReversalByIterator(){

        if (firstNode == null || firstNode.next == null){
            return;
        }

        Node<E> currentNode = firstNode;
        Node<E> preNode = null;
        Node<E> nextNode;

        /**
         * 这里不能使用 current.next != null，current.next == null为最后一个node的next赋值
         */
        while (currentNode != null){

            nextNode = currentNode.next;
            currentNode.next = preNode;
            preNode = currentNode;
            currentNode = nextNode;
        }

        /**
         * 由于上面的currentNode 退出循环，所以使用 preNode 作为第一个节点
         */
        firstNode = preNode;
    }

    private Node<E> doReversalByRecursion(Node<E> node){

        if (node == null || node.next == null) {

            return node;
        }

        Node<E> firstNode = doReversalByRecursion(node.next);

        node.next.next = node;
        /**
         * 这里把node的next赋值为null，本next的值在上层函数调用中保存了
         *
         */
        node.next = null;
        return firstNode;
    }

    private Node<E> elementOf(int index){

        checkIndex(index);

        Node<E> tmpNode = firstNode;
        for (int i = 0; i < size; i++) {

            if (i == index){

                return tmpNode;
            }
            tmpNode = tmpNode.next;
        }

        return null;
    }


}
